package com.computer.fundamentals.algorithm;

import java.util.HashMap;
import java.util.Map;

/**
 * 经典问题：大数加法
 *  --------------------------------------------------------------------------------
 *  36进制由0-9，a-z，共36个字符表示。
 *  要求按照加法规则计算出任意两个36进制正整数的和，如1b + 2x = 48  （解释：47+105=152）
 *  注意：不允许使用先将36进制数字整体转为10进制，相加后再转回为36进制的做法
 *  --------------------------------------------------------------------------------
 */
public class IntegerInquiry {

    /**
     * 36进制大数加法实现
     */
    public static String solution(String num1, String num2) {
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0;i <= 9;i++) {
            map.put((char) ('0' + i), i);
        }
        for (int i = 0;i <= 25;i++) {
            map.put((char) ('a' + i), i+10);
        }
        int n1 = num1.length(), n2 = num2.length();
        char[] res = new char[Math.max(n1, n2) + 1];
        int i = n1-1, j = n2-1, k = Math.max(n1, n2);
        int carry = 0;
        while (i >= 0|| j >= 0 || carry != 0) {
            int tmp1 = (i < 0) ? 0 : map.get(num1.charAt(i));
            int tmp2 = (j < 0) ? 0 : map.get(num2.charAt(j));
            int tmp = tmp1 + tmp2 + carry;
            res[k--] = (tmp % 36 >= 10) ? (char) ('a' + tmp % 36 - 10) : (char) ('0' + tmp % 36);
            carry = tmp / 36;
            i--;
            j--;
        }
        k = 0;
        if (res[k] == '\u0000') {
            k++;
        }
        return new String(res, k, Math.max(n1, n2) + 1 - k);
    }

    /**
     * 测试
     */
    public static void main(String[] args) {
        System.out.println(solution("love", "peace"));
    }

}
